package 力扣热题100;
/**
 * 三数之和
 * 此题用排列加双指针
 * 最为关键的是去重
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode8 {
    List<List<Integer>>list1=new ArrayList<>();
    private void find(int[] nums, int num,int k) {
        int l=k+1;
        int r=nums.length-1;
        while (l<r){
            int sum=nums[r]+nums[l]+num;
            if(sum==0){
                List<Integer>list=new ArrayList<>();
                list.add(nums[l]);
                list.add(num);
                list.add(nums[r]);
                list1.add(list);
                while(l<r&&nums[r]==nums[--r]);
                while(l<r&&nums[l]==nums[++l]);
            }else if(sum>0){
                while(l<r&&nums[r]==nums[--r]);
            }else {
                while(l<r&&nums[l]==nums[++l]);
            }
        }
    }
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums==null) {
            return list1;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(i-1>=0&&nums[i-1]==nums[i]){
                continue;
            }
            if(nums[i]>0){
                return list1;
            }
            find(nums,nums[i],i);
        }
        return list1;
    }

    public static void main(String[] args) {
        int[]arr={-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
        LeetCode8 leetCode8=new LeetCode8();
        leetCode8.threeSum(arr);
    }
}
